package lcr;

public class Test0071 {
}

class Solution0071_1 {
    int[] preSum;
    int sum;
    public Solution0071_1(int[] w) {
        sum=0;
        preSum=new int[w.length];
        for (int i = 0; i < w.length; i++) {
            sum+=w[i];
            preSum[i]=sum;
        }
    }

    public int pickIndex() {
        int target = (int) (Math.random() * sum)+1;
        return binarySearch(target);
    }

    public int binarySearch(int target){
        int left=0, right=preSum.length-1;
        while (left<right){
            int mid=(left+right)>>1;
            int num = preSum[mid];
            if (num>target){
                right=mid;
            } else if (num < target) {
                left = mid + 1;
            }else {
                return mid;
            }
        }

        return left;
    }
}
